package a202110.day06;

/**
 * 数字的补数
 * <p>
 * 对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
 * 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
 * 给你一个整数 num ，输出它的补数。
 * <p>
 * 输入：num = 5
 * 输出：2
 * 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
 * <p>
 * 输入：num = 1
 * 输出：0
 * 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
 * <p>
 * 提示:
 * 1 <= num < 231
 *
 * @author yousj
 * @since 2021/10/18
 */
public class Main {

    public static void main(String[] args) {
        // 思路
        // 找到大于num的最小的2的幂次方数-1
        // 这样得到的数字的二进制位为全1
        // 然后与num做异或运算
        System.out.println(findComplement(5));
    }

    private static int findComplement(int num) {
        int temp = num, c = 0;
        while (temp > 0) {
            temp = temp >> 1;
            c = (c << 1) + 1;
        }
        return num ^ c;
    }

    private static int findComplement1(int num) {
        int n = num;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n ^ num;
    }

    private static int findComplement2(int num) {
        // Integer.highestOneBit(num) 得到的是 num 对应的二进制最高位为 1 ，其余位都为 0 时的数值
        // 或者说是小于 num 的最大的 2 的幂次方，例如 5 -> 4，25 -> 16，45 -> 32
        // 往左移 1 位再减 1 得到的就是两个数的异或结果
        // 把上一步得到的数值跟 num, 异或就得到答案了
        return (((Integer.highestOneBit(num) << 1)) - 1) ^ num;
    }

}
